/*
 * @lc app=leetcode.cn id=40 lang=cpp
 *
 * [40] 组合总和 II
 *
 * https://leetcode.cn/problems/combination-sum-ii/description/
 *
 * algorithms
 * Medium (60.70%)
 * Likes:    1003
 * Dislikes: 0
 * Total Accepted:    307.4K
 * Total Submissions: 506.6K
 * Testcase Example:  '[10,1,2,7,6,1,5]\n8'
 *
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 *
 * 注意：解集不能包含重复的组合。 
 *
 *
 *
 * 示例 1:
 *
 *
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 输出:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 *
 * 示例 2:
 *
 *
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 输出:
 * [
 * [1,2,2],
 * [5]
 * ]
 *
 *
 *
 * 提示:
 *
 *
 * 1 <= candidates.length <= 100
 * 1 <= candidates[i] <= 50
 * 1 <= target <= 30
 *
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> sequence;

public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        // 按从小到大排序
        sort(candidates.begin(), candidates.end());
        // 构造freq数组，freq存储的是key-value对，分别是数字的值及其出现的次数
        for (int num : candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1);
            }
            else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ans;
    }

    // helper
    void dfs(int pos, int rest) {
        // 已经组成了target，输出sequence
        if (rest == 0) {
            ans.push_back(sequence);
            return;
        }
        // 剩下的数字都比rest大，遂无法成功
        if (pos == (int)freq.size() || rest < freq[pos].first) {
            return;
        }
        // 不选当前pos的值
        dfs(pos + 1, rest);
        // 处理重复情况的步骤，most为pos位置的元素最多选取的数目，用for循环，对每种情况分别做dfs
        int most = min(rest / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= most; ++i) {
            sequence.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        // 回改当前状态
        for (int i = 1; i <= most; ++i) {
            sequence.pop_back();
        }
    }
};
// @lc code=end
